<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">

<head>
	<meta http-equiv="content-type" content="text/html;charset=utf-8" />
	<title>AXL Tutorial: TranzAm</title>
	<link href="style.css" rel="stylesheet" type="text/css" />
</head>
<body>
<!-- menu -->
	<div id="navmain">
	<ul>
		<li><a href="index.html">Overview</a></li>
		<li><a href="install.html">Installation</a></li>
		<li><a href="config.html">Configurator</a></li>
		<li><a href="animation.html">Animation</a></li>
		<li><a href="framework.html">Framework</a></li>
		<li><a href="tranzam.html">Tutorial</a></li>
	</ul>
	</div>
	<div id="navsub">
	<ul>
		<li><a href="tranzam.html">Start</a></li>
		<li><a href="tranzam_a1.html">Article 1</a></li>
		<li><a href="tranzam_a2.html">Article 2</a></li>
		<li><a href="tranzam_a3.html">Article 3</a></li>
		<li><a href="tranzam_a4.html">Article 4</a></li>
		<li><a href="tranzam_a5.html">Article 5</a></li>
		<li><a href="tranzam_a6.html">Article 6</a></li>
		<li><a href="tranzam_a7.html">Article 7</a></li>
		<li><a href="tranzam_a8.html">Article 8</a></li>
		<li><a href="tranzam_a9.html">Article 9</a></li>
		<li><a href="tranzam_a10.html">Article 10</a></li>
	</ul><span class="smallprint">This menu will stay fixed with a proper browser.</span>
	<p>
	 <a href="http://jigsaw.w3.org/css-validator/">
	  <img style="border:0;width:88px;height:31px"
		   src="http://jigsaw.w3.org/css-validator/images/vcss" 
		   alt="Valid CSS!" />
	 </a>
	</p>
	<p>
      <a href="http://validator.w3.org/check?uri=referer"><img
          src="http://www.w3.org/Icons/valid-xhtml10"
          alt="Valid XHTML 1.0!" height="31" width="88" /></a>
    </p>
<p><a href="http://www.bloggerheads.com/bbc/"><img src="http://www.bloggerheads.com/bbc/bbc.gif" width="90" height="45"  
alt="Click here to find out why." /></a></p>
<p><a href="http://retrospec.sgn.net" ><img src="retrospec.gif" width="150" alt="Fine games" /></a></p>
	</div>
<!-- menu -->

	<div id="main">
	<a name="files"></a>
<h1>Introduction</h1>
In the previous lesson we added the enemies. This lesson is a departure from the game to learn about the A* path-finding algorithm. 
The idea being that we can concentrate purely on path finding without the complexity of the game.
<br />There are actually two projects/makefiles in this lesson:
<ul>
<li>The first contains no A* at all, purely a little program to draw a maze and random blocks</li>
<li>the second contains the A* path-finding</li>
</ul>
It is done like this so that we can differentiate between path-finding and the program that uses the path finding.
<h1>Test 1: Structure</h1>
If you are manually creating the project 
    make file then use the one from lesson 8, delete all the game_*.* files and mappyal.c (i.e. just leave the axl*.* files) and then add
	test1.cpp. The end result is a makefile that compiles the following files: axl_animations.cpp, axl_config.cpp, axl_framework.cpp, test1.cpp
<br /><strong>Note: </strong>Alternatively there is a version of test1.cpp, called test1_no_axl.cpp, that is pure allegro code and does not use the AXL system. 
i.e. you can just compile the one source file (with allegro). This is useful if you are here not for the TransAm tutorial, but somehow found this A* tutorial.
<h1>Test 1: Objectives</h1>
<img src="images/tranzam_maze.jpg" alt="maze" style="float: right; padding-left="20px" />
In test 2 we will be programming an A* path-finding system - i.e. generating the best possible route from A to B, avoiding obstacles. We will do this by creating a simple 
program that lets the user draw random blocks on the screen and a start/end point. Just to make it more interesting we will be adding a maze generator as well.
<br />
The program will let the user generate one of two blocks (a wall and a hedge) that cannot be passed. They are both treated the same within the program, they are here 
purely to show that you can have different block types in your map.
<br />
Compile/run the program and have a play. You can see that there are various methods of filling in the map - by hand, by randomness, by a maze generator. When we integrate
the A* path-finding code we will be generating a path from the start (S) to the end (E).
<h1>Test 1: Map</h1>
The map is a 2-dimensional array, <span class="code">int MapGame[MapHeight][MapWidth]</span>. The size is 29x30 blocks. We will not be explaining the main() function as it is just a 
standard function to run the program. The map is this size because we are drawing to a 640x480 screen and need space for the menu.
<br />InitialiseData() method creates our two bitmaps for the blocks that populate the map (hedge/wall - each block is 16x16 pixels), and empties the map using ClearGameMap function.
<br />
Our map consists of an array of integers, that can be either 0 (empty), 1 (a wall), or 2 (a hedge). When we place a hedge or a wall or clear the cell we simply update the 
array with that value, this is shown in the ProcessKeys function for SETNONE, SETWALL, SETHEDGE.
<br />
The random options simply clears the map then places random blocks on it.
<h1>Test 1: Maze</h1>
The maze is a class called Grid. The Grid class is defined in the test1.h file. Internally it consists of linked list (MazeSquare) that contains x/y co-ordinates.
<br />The method of creating a maze is as follows, and contained within the GenerateMaze function:
<ol>
<li>Create a new Grid object passing in the size of your maze and an array of that size. In our case we are passing in our Map (MapGame variable).</li>
<li>Tell the Grid the create a maze (Grid::GenerateMaze method)</li>
<li>Retrieve the start and end Y locations using Grid::GetStartY and Grid::GetGoalY methods</li>
<li>In our maze we are always using the leftmost and rightmost edges of the maze for the start and end point</li>
</ol>
Calling GenerateMaze populates the array you passed in with either 1 (a solid block) or a 0 (an empty block).
<br />
The internals of the maze are not necessary for using the program (or generatting your own maze), but you can see that it's pretty straightforward and will easily integrate into any code.<br />
However, it works by using a path-growing (randomised depth-first) algorithm. Note, if you look at the Grid::GenerateMaze method you can uncomment the random seed to produce random mazes 
every time. I just left it out as having the same first maze seemed the best thing to do for this program - you also need time.h if using the seeder.
<br />
For information on various maze generating algorithms, see <a href="http://en.wikipedia.org/wiki/Maze_generation">wikipedia</a><br />


<h1>Test 2: Structure</h1>
If you are manually creating the project 
    make file then use the one above but change the source file from test1.cpp to test2.cpp
<br /><strong>Note: </strong>Alternatively you there is a version of test2.cpp, called test2_no_axl.cpp, that is pure allegro code 
and does not use the AXL system. 
i.e. you can just compile the one source file (with allegro). This is useful if you are here not for the TransAm tutorial, but somehow found this A* tutorial.
<h1>Test 2: Objectives</h1>
In this lesson we will be applying the A* path-finding algorithm to the code to find a path from the start (S) tile to the end (E) tile.
<br />First, compile the code and run it. There are two new options available:
<ol>
<li>Generate Route 1: this generates a path and allows diagonal (8-way) movement</li>
<li>Generate Route 2: this generates a path and only allows straight (4-way) movement</li>
</ol>
<img src="images/tranzam_astar.jpg" alt="astar"" />
<h1>Test 2: AStar Algorithm</h1>
Firstly, an apology for those who know a lot more than me. What follows is a simple guide to A* and by no means represents a thorough 
analysis and may contain some inaccurate information!<br />
AStar algorithms determine a route by taking two factors into account. The first is the distance it has already travelled, and the second is 
a 'heuristic' (a guess) to estimate the distance to the goal. While it is the distance already travelled that makes the A* algorithm 
better than other path-finding algorithms (e.g. Dijkstra's algorithm that searches in all directions regardless), it is the heuristic that
provides the algorithm with the choices of where to go next. A drawback of this algorithm is that it will always pick the shortest route, 
which may not be as aesthetically pleasing as you might hope for. 
<br />
The formula applied (in finding the path) seems rather simple on the outset: f=g+h. 'h' is the heuristic and 'g' is the distance already travelled. 
What this gives us is a score for each node. From this it can work out the best path by discounting the high value 'f' values for each node.
What the AStar class does is generate a list of possible paths, then picks the best one. These are sometimes called the 'open' and 'closed' lists, i.e. 
it knows which nodes (locations) it has been to and which ones it hasn't and uses these to determine which way to go next in searching.
<br />
As you might think, it is the 'h' (the heuristic) that both determines the speed and the accuracy of the search. If we didn't use 'h'
then we'd end up with Dijkstra's method which will find the shortest path, but at the expense of doing a very wide search. This means the lower 
we set 'h' the more nodes are searched and the more accurate the search, but takes longer, and the higher we set 'h' the less nodes are searched
and the less accurate the search, but it is much faster. 
<br />
One way of speeding up the search is to use waypoints, i.e. instead of searching the entire map for a path, have a number of locations 
on the map that we can use instead and whatever object is using the path-finding will navigate between the waypoints it knows about.
Obviously, how wide an area you do a search (A to B route) is a major factor that determines the speed 
of the algorithm, which is probably best tested in code. However an area of 40 tiles is not an unreasonable amount.

<h2>Heuristics</h2>
There are a number of ways of calculating this heuristic:
<ul>
<li>Manhatten: Most A* routines use this. It is the minimum distance from where we are (i) to the goal (j), e.g. (i.x-j.x)+(i.y-j.y) - this is usually multiplied by a factor representing the cost of moving a standard space. This is a 4-directional method only</li>
<li>Diagonal: Similar to Manhatten but allows diagonal movement, calculated by the max of x and y
<li>Euclidean: If we can use any angle, rather than fixed tiles then we can use pythagorus</li>
</ul>
For further information I'd recommend you visit one of the links below, the first one (Patrick Lester) is 
particularly pleasing to us with smaller brains.
<h2>Links</h2>
<ul>
<li><a href="http://www.policyalmanac.org/games/aStarTutorial.htm">Patrick Lester</a> : This is my favourite as it's explains things graphically and simply
<li><a href="http://www-cs-students.stanford.edu/~amitp/gameprog.html">Amit's</a> : Probably the most read and exhaustive collection of A* and path-finding tutorials</li>
<li><a href="http://www.geocities.com/jheyesjones/astar.html">Justin Heyes-Jones</a> : A quick intro to A*, but more importantly has a unique
way of implementing A* by using it to solve a sliding puzzle game rather than a tile map for a game</li>
</ul>

<h1>Test 2: Objectives</h1>
To put it in context, we (hopefully) want a black-box solution that will give us a path from A to B. 
We want the solution to be as simple and easy to use as possible, and we want to be able to modify the code
to match any of our requirements (e.g. changing the heuristic).
<br />
The algorithm supplied should hopefully do that, and to use it we do the following:
<ul>
<li>Generate an array of integers representing blocked and open tiles (i.e. tile locations that we can go through and tile locations we cannot)</li>
<li>Create an object of type AStarClass (this is our AStar algorithm) giving it our map as a read-only reference so that it can generate it's own internal representation</li>
<li>Repopulate the array/inform the AStarClass whenever the map it represents changes, e.g. a once open tile becomes blocked)</li>
<li>Call an AStarClass method (in our case NewPath) to generate a path between the given start and end locations</li>
<li>To navigate the path we can use some AStarClass methods such as NodeGoFirst, ReachedGoal, PathNextNode, NodeGetX and NodeGetY</li>
</ul>
These are all described next.
<h1>Test 2: Code Walk-Through</h1>
In the header file, test2.h, we are adding three functions to wrap up the AStarClass algorithm:
<ul>
<li>GenerateAStar: This will generate our path</li>
<li>ReInitialiseStarMap: this will update the map array</li>
<li>DrawAStarRoute: traverses the path to draw the route on the screen</li>
</ul>
The A* routine needs (read-only, it does not modify) an array representing the tile map. It is a simple integer based array representing zero for 
empty tiles and any non-zero for a blocked tile. Although in our maze this is all our map consists of and we could simply pass in our maze 
array, in the Trans-Am game, the the map is much more complicated so we will be generating a simpler version. For this reason we are doing the same in this lesson.
<br />Obviously this means we cannot add weightings for different tiles, but that is easily modifiable, and is described below. Whether 
we do this in the game remains to be seen :)
<br />The variable <span class="code">MapAstar[MapHeight*MapWidth]</span> is created and matches that of our MapGame we are using for the maze.
</br />
In other words, we have our version of the map (MapGame) and an AStarClass friendly version (MapAstar), and we need to keep
them synchronised. In the TransAm game MapGame will be the Mappy map, which is much more complicated, and shows 
why we need to have the two different versions (described in the next lesson).
<br />We initialise the array by matching array elements with the maze array, storing 1 or 0 for a tile or no tile. This is handled by the function 
ReinitialiseStarMap and is called on starting the program and every time the A* map is generated:
<div class="code">
void ReInitialiseStarMap()
{
for(int i=0;i&lt;MapHeight;i++)
	for(int j=0;j&lt;MapWidth;j++)
	{
		MapAstar[i*MapWidth+j]=(MapGame[i][j]?1:0);
	}
	MapGenerated=false;
}</div>

Our A* algorithm is represented by the class AStarClass and is held entirely in the files game_astar.h and game_astar.cpp.
 Note, the two arrays are the same, just the AStarClass version is a 1-dimensional array rather than 2-dimensional<br />
Whenever we want to generate a path we call our GenerateAStar function (that takes a parameter to indicate if diagonal movement is allowed).
This function firstly calls the ReInitialiseStarMap function to regenerate the array, we then call the AStar method, RedoAstarTileMap, passing in our array. This 
initialises our A* object ready for path-finding. When we want to generate a path we call the member function NewPath, passing in the 
start and end X/Y locations and the diagonal flag:
<div class="code">
ReInitialiseStarMap();
MyAStar-&gt;RedoAstarTileMap(MapAstar);
if(!MyAStar-&gt;NewPath(StartX*BlockSize,StartY*BlockSize,EndX*BlockSize,EndY*BlockSize,allowdiagonal))
	MessageBox("Computer Says No");
else		
	MapGenerated=true;
</div>
The only odd thing there is the BlockSize multiplier. When we initialised our astar class we passed in the size of the array and 
the size of each tile. The A* algorithm we are using works in pixels. This will become apparent when we integrate the A* algorithm into 
the game.
<br />
In our MazeDraw function we call DrawAStarRoute. In this function we traverse our A* object's found path and for each item (known as a node),
we output a '*' at it's location. We traverse the path as follows:
<div class="code">
MyAStar-&gt;NodeGoFirst();
while( !MyAStar-&gt;ReachedGoal())
{
	x  =  XOffset+MyAStar-&gt;NodeGetX();
	y  =  YOffset+MyAStar-&gt;NodeGetY();
	textout_ex(GameFramework-&gt;DrawingSurface,font,"*",x,y,makecol(0,255,0),-1);
	MyAStar-&gt;PathNextNode();
</div>
NodeGoFirst() resets the path to the first item, ReachedGoal() tells us if we have reached the end, NodeGetX/NodeGetY retrieves 
the node's x/y location in pixels, PathNextNode() goes to the next item in the list. In our code we have a few extra 
lines of code to stop the '*' from overwriting our map labels 'S' and 'E'
</br>

<h2>Recap</h2>
<ul>
<li>Create a integer based array for representing the map</li>
<li>Create AStarClass object giving it the array as a reference point</li>
<li>If we ever change the map, call RedoAStarTileMap method</li>
<li>To generate the call the NewPath method</li>
<li>To navigate the found path use ReachedGoal method to see if we are there, use PathNextNode method to go to the next
node, use NodeGetX/Y methods to retrieve the x/y location in the node we are in. All locations are in pixels</li>
<li></li>
</ul>

<h2>Modifications</h2>
If we wish to alter the algorithm to take into account weighted tiles (e.g. some tiles may be passable but have a higher cost, e.g. represents 
a tile that slows down the player), we need to alter the AStar class:

<ul>
<li>The heuristic (h) is calculated using the hypotenuse method. This is shown in the FindPath method of the AstarClass, as well as the GenerateSucc method. Either adjust these lines or the 'distance' method. In the code you will see two versions of distance, the commented version returns the pythag version, the uncommented the Manhatten.</li>
<li>Weightings can be added by multiplying all references to g and h (i.e. '->g' and '->h' in the code) by the TileMap value. TileMap is it's array taken from our map array</li>
<li></li>
</ul>
To be honest, the 'diagonal' flag passed in to the AStar algorithm NewPath should really alter the heuristic
to calculate using Manhatten or Diagonal. What it actually does is calls the same euclidean (pythagorus method) 
but skips checking the diagonal nodes.
</ul>
<h1>Allegro</h1>
Just to recap, we've learnt a little bit about the A-Star algorithm and made a program to test it out.
<h1>Next</h1>
The next lesson  we will be using the code from this lesson and applying it to our game to find 
the best path from the enemy cars to the player.<br /></div>
</body>
</html>
